import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-04-21
 * Time: 21:15
 */
class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Test {
    //TOP-K方法(在堆中找到前k个最小值并且输出)
    public static int[] smalLeastK1(int[] arr , int k){
        //方法1(创建小根堆,前面几个肯定是最小的)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    //方法2(先排序，再取出前k个元素，即为前k个最小元素)

    //方法3(把前k个元素创建成大根堆，遍历剩下的n-k个元素，和堆顶的元素比较，如果比堆顶的元素较小，则入堆，堆顶元素删除)
    public static int[] sallLeastK3(int[] arr, int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new IntCmp());

        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length ;i++) {
            int peekVal = priorityQueue.peek();
            if(peekVal > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] array = { 12 , 23 , 34 , 45 ,56 ,67 , 78 , 89 , 90 , 100};
        int[] ret1 = smalLeastK1(array, 3);
        for(int x : ret1){
            System.out.print(x + " ");
        }

        System.out.println();

        int[] ret2 = sallLeastK3(array, 3);
        for(int x : ret2){
            System.out.print(x + " ");
        }
    }
    public static void main2(String[] args) {
        //测试java中自带的优先级队列
        //默认小根堆创建
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        System.out.println("小根堆");
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(3);
        priorityQueue.offer(4);

        System.out.println(priorityQueue.peek());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.peek());

        //通过传入新的比较器来创建大根堆
        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new IntCmp());

        System.out.println("大根堆");
        priorityQueue2.offer(1);
        priorityQueue2.offer(2);
        priorityQueue2.offer(3);
        priorityQueue2.offer(4);

        System.out.println(priorityQueue2.peek());
        System.out.println(priorityQueue2.poll());
        System.out.println(priorityQueue2.peek());
    }

    //测试myheap
    public static void main1(String[] args) {
        int[] array = { 12 , 23 , 34 , 45 ,56 ,67 , 78 , 89 , 90 , 100};
        MyHeap myHeap = new MyHeap();

        myHeap.initElem(array);

        myHeap.creatHrap();

        myHeap.offer(22);

        myHeap.heapSort();
        System.out.println(myHeap.poll());
    }
}
